package com.hanxiaozhang.no10leetcode.tree;

import javax.xml.namespace.QName;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * 〈一句话功能简述〉<br>
 * 〈〉
 * 给一棵二叉树，判断是否是一棵正确的二叉搜索树
 * 二叉搜索树定义如下：
 * - 左子树的节点都要小于根节点 右子树的节点都要大于根节点 左子树和右子树都必须是二叉搜索树。
 * - 搜索二叉树不能有一样的数值。
 * 实例1:
 * . 2
 * ./ \
 * 1   3
 * 输入: [2,1,3]
 * 输出: true
 * <p>
 * 实例2:
 * .     5
 * .    /  \
 * .   1    4
 * .       / \
 * .      3   6
 * 输入: [5,1,4,null,null,3,6]
 * 输出: false
 * 解析: 根节点的值为5，但其右侧子节点的值是4。
 * <p>
 * 思路（方法1）：-> 二叉搜索树的中序遍历必定是升序的
 * 1.将二叉树中序存入List中。
 * 2.判断List中数据，是否为升序
 *
 * @author hanxinghua
 * @create 2024/3/21
 * @since 1.0.0
 */
public class No98ValidateBinarySearchTree {

    public static void main(String[] args) {

        TreeNode tree1 = new TreeNode(2);
        tree1.left = new TreeNode(1);
        tree1.right = new TreeNode(3);

        TreeNode tree2 = new TreeNode(5);
        tree2.left = new TreeNode(1);
        tree2.right = new TreeNode(4);
        tree2.right.left = new TreeNode(3);
        tree2.right.right = new TreeNode(6);

        System.out.println(method1(tree1));
        System.out.println(method1(tree2));

        TreeNode tree3 = new TreeNode(5);
        tree3.left = new TreeNode(4);
        tree3.right = new TreeNode(6);
        tree3.right.left = new TreeNode(3);
        tree3.right.right = new TreeNode(7);
        System.out.println(method3(tree3));

        System.out.println("---- ---- ---- ----");

        Integer[] arrs1 = {2, 1, 3};
        Integer[] arrs2 = {5, 1, 4, null, null, 3, 6};
        System.out.println(method_ext(arrs1));
        System.out.println(method_ext(arrs2));

    }

    /**
     * 方法1：二叉搜索树的中序遍历必定是升序的。
     * 重点
     *
     * @param root
     * @return
     */
    private static Boolean method1(TreeNode root) {

        List<Integer> list = middleRecurse(root);

        for (int i = 1; i < list.size(); i++) {
            if (list.get(i - 1) > list.get(i)) {
                return false;
            }
        }
        return true;

    }


    /**
     * 方法2 （先放弃这种方法 ）
     * 思路：利用搜索二叉树的性质，判断是否为搜索二叉树。即对于任意结点：
     * 左子树的节点都要小于根节点，右子树的节点都要大于根节点。
     *
     * @param root
     * @return
     */
    public static boolean method2(TreeNode root) {
        if (root == null) {
            return true;
        }
        return check(root, null, null);
    }

    /**
     * 递归比较
     *
     * @param node  当前节点
     * @param lower 最低值
     * @param upper 最大值
     * @return
     */
    private static boolean check(TreeNode node, Integer lower, Integer upper) {
        // 边界条件1
        if (node == null) {
            return true;
        }
        int val = node.val;
        // 边界条件2
        if (lower != null && val <= lower) {
            return false;
        }
        // 边界条件2
        if (upper != null && val >= upper) {
            return false;
        }
        // 左孩子结点 小于 当前节点的值    &&   右孩子节点  大于 当前节点的值
        return check(node.left, lower, val) && check(node.right, val, upper);
    }

    /**
     * 拓展
     * 这种写法只考虑了局部保证BST要求，没有考虑到整体上BST要求，先pass
     *
     * @param root
     * @return
     */
    @Deprecated
    private static boolean method3(TreeNode root) {
        if (root == null) {
            return true;
        }

        return recursion(root);
    }

    @Deprecated
    private static boolean recursion(TreeNode root) {
        if (root == null) {
            return true;
        }
        if (root.left != null && root.left.val >= root.val) {
            return false;
        }
        if (root.right != null && root.right.val <= root.val) {
            return false;
        }

        return recursion(root.left) && recursion(root.right);
    }


    // ---- ---- ---- ---- ---- ---- ----


    /**
     * 拓展。判断二叉树按层存储数组，是否为搜索二叉树
     *
     * @param arrs
     * @return
     */
    private static Boolean method_ext(Integer[] arrs) {

        // 1.数组存入队列（目的：为数组转换成二叉树做准备）
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < arrs.length; i++) {
            queue.add(arrs[i]);
        }

        // 2.将数组转成二叉树数
        Queue<TreeNode> helpQueue = new LinkedList<>();
        TreeNode root = gTreeNode(queue.poll());
        helpQueue.add(root);

        while (!helpQueue.isEmpty()) {

            TreeNode node = helpQueue.poll();
            node.left = gTreeNode(queue.poll());
            node.right = gTreeNode(queue.poll());

            if (node.left != null) {
                helpQueue.add(node.left);
            }

            if (node.right != null) {
                helpQueue.add(node.right);
            }
        }

        // 3. 将二叉树中序遍历，存入集合
        List<Integer> list = middleRecurse(root);

        // 4. 判断中序集合是否为升序
        for (int i = 1; i < list.size(); i++) {
            if (list.get(i - 1) > list.get(i)) {
                return false;
            }
        }
        return true;
    }

    private static List<Integer> middleRecurse(TreeNode root) {

        List<Integer> results = new ArrayList<>();

        middle(root, results);

        return results;
    }


    private static void middle(TreeNode node, List<Integer> results) {
        if (node == null) {
            return;
        }
        middle(node.left, results);
        results.add(node.val);
        middle(node.right, results);
    }


    /**
     * 生成节点
     *
     * @param val
     * @return
     */
    private static TreeNode gTreeNode(Integer val) {

        if (val == null) {
            return null;
        }
        return new TreeNode(val);
    }


}
